<!DOCTYPE HTML PUBliC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
  <head>
    <title>fastutil</title>
  </head>

  <body>

    <p>Extends the the <a href="http://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html">Java&trade; Collections Framework</a>
    by providing type-specific maps, sets, lists and priority queues with a small memory
    footprint and fast access and insertion; provides also big (64-bit) arrays, sets and lists, and
    fast, practical I/O classes for binary and text files. It is
    free software
    distributed under the <a HREF="http://www.apache.org/licenses/LICENSE-2.0.html">Apache License 2.0</a>.



    <h1>Package Specification</h1>

    <p><code>fastutil</code> is formed by three cores:
    <ul>
    <li>type-specific classes that extend naturally
    the <a href="http://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html">Java&trade; Collections Framework</a>;
    <li>classes that support very large collections;
    <li>classes for fast and practical access to binary and text files.
    </ul>
    <p>The three cores are briefly introduced in the next sections, and then discussed at length in the rest of this overview.

    <p>The following features were added in version 8.5.0:

	<ul>
	<li>type-specific {@linkplain java.util.Spliterator spliterators};
	<li>primitive {@linkplain java.util.stream.Stream stream} methods;
	<li>even more default methods overridden for performance or avoiding boxing/unboxing.
	</ul>

	<p>We <strong>strongly suggest</strong> to activate deprecation warnings in your development environment, as <code>fastutil</code>
	systematically deprecates all JDK methods for which there is a type-specific alternative.

    <h2>Type-specific classes</h2>

    <p><code>fastutil</code> specializes the most useful {@link
    java.util.HashSet}, {@link java.util.HashMap}, {@link
    java.util.LinkedHashSet}, {@link java.util.LinkedHashMap}, {@link
    java.util.TreeSet}, {@link java.util.TreeMap}, {@link
    java.util.IdentityHashMap}, {@link java.util.ArrayList} and {@link
    java.util.Stack} classes to versions that accept a specific kind of
    key or value (e.g., {@linkplain it.unimi.dsi.fastutil.ints.IntSet integers}). Besides, there are also
    several types of {@linkplain it.unimi.dsi.fastutil.PriorityQueue priority
    queues} and a large collection of static objects and
    methods (such as {@linkplain it.unimi.dsi.fastutil.objects.ObjectSets#EMPTY_SET
    immutable empty containers}, {@linkplain
    it.unimi.dsi.fastutil.ints.IntComparators#OPPOSITE_COMPARATOR
    comparators implementing the opposite of the natural order},
    {@linkplain it.unimi.dsi.fastutil.ints.IntIterators#wrap(int[])
    iterators obtained by wrapping an array} and so on).</p>

    <p>To understand what's going on at a glance, the best thing is to look at
    the examples provided below. If you already used the
    Collections Framework, everything should look
    rather natural. If, in particular, you use an IDE that can suggest you the
    method names, all you need to know is the right name for
    the class you need.


    <h2>Support for very large collections</h2>

    <p>A set of classes makes it possible
    to handle very large collections: in particular, collections whose size exceeds
    2<sup>31</sup>. {@linkplain it.unimi.dsi.fastutil.BigArrays Big arrays}
    are arrays-of-arrays handled by a wealth of static methods that act on them
    as if they were monodimensional arrays with 64-bit indices;
    {@linkplain it.unimi.dsi.fastutil.BigList big lists} provide 64-bit list access;
    {@linkplain it.unimi.dsi.fastutil.ints.IntOpenHashBigSet big hash sets} provide support for sets whose
    size is only limited by the amount of core memory.

    <p>The usual methods from {@link java.util.Arrays} and similar classes have
    been extended to big arrays: have a look at the Javadoc documentation of
    {@link it.unimi.dsi.fastutil.BigArrays} and {@link it.unimi.dsi.fastutil.ints.IntBigArrays}
    to get an idea of the generic and type-specific methods available.

	<p>Limited support is available for big atomic arrays of integers and longs.

    <h2>Fast and practical I/O</h2>

    <code>fastutil</code> provides replacements for some standard classes of {@link java.io}
    that are plagued by a number of problems (see, e.g., {@link it.unimi.dsi.fastutil.io.FastBufferedInputStream}).
    The {@link it.unimi.dsi.fastutil.io.BinIO} and {@link it.unimi.dsi.fastutil.io.TextIO} static
    containers contain dozens of methods that make it possible to load and save quickly
    (big) arrays to disks, to adapt binary and text file to iterators, and so on.
	Classes such as {@link it.unimi.dsi.fastutil.ints.IntMappedBigList} make it possible
    to map into memory large file of primitive types and access them as {@linkplain it.unimi.dsi.fastutil.BigList big lists}.

    <h1>More on type-specific classes</h1>

    <p>All data structures in <code>fastutil</code> extend their standard
    counterpart interface whenever possible (e.g., {@link java.util.Map} for maps). Thus, they
    can be just plugged into existing code, using the standard access methods. However, they also provide
    (whenever possible) many polymorphic versions of the most used methods that
    avoid boxing/unboxing. In doing so, they specify more stringent interfaces that
    extend and strengthen the standard ones (e.g., {@link
    it.unimi.dsi.fastutil.ints.Int2IntSortedMap} or {@link
    it.unimi.dsi.fastutil.ints.IntListIterator}). All generic methods
    in type-specific interfaces have been deprecated.</p>

    <p><strong>Warning</strong>: automatic boxing and unboxing can lead you
    to choose the wrong method when using <code>fastutil</code>. It is also extremely inefficient.
    We suggest that your programming environment is set so to mark boxing/unboxing as
    a warning, or even better, as an error.

    <p>The main point of type-specific data structures is that the
    absence of wrappers around primitive types can increase speed and reduce
    space occupancy by several times. The presence  of generics in Java
    does not change this fact, since there is no genericity for primitive
    types.

    <p>The implementation techniques used in <code>fastutil</code> are quite
    different than those of {@link java.util}: for instance, open-addressing
    hash tables, threaded AVL trees, threaded red-black trees and exclusive-or
    lists. An effort has also been made to provide powerful derived objects and
    to expose them by overriding covariantly return types:
    for instance, the {@linkplain it.unimi.dsi.fastutil.objects.Object2IntSortedMap#keySet() keys of sorted maps
    are sorted} and iterators on sorted containers are always {@linkplain
    it.unimi.dsi.fastutil.BidirectionalIterator bidirectional}.

    <p>More generally, the rationale behing <code>fastutil</code> is that
    <em>you should never need to code explicitly natural
    transformations</em>. You do to not need to define an anonymous class to
    iterate over an array of integers&mdash;just {@linkplain
    it.unimi.dsi.fastutil.ints.IntIterators#wrap(int[]) wrap it}. You do not
    need to write a loop to put the characters returned by an iterator into a
    set&mdash;just {@linkplain
    it.unimi.dsi.fastutil.chars.CharOpenHashSet#CharOpenHashSet(CharIterator)
    use the right constructor}. And so on.

    <h2>The Names</h2>

    <p>In general, class names adhere to the general pattern</p>

    <div style="padding: 1em">
      <var>valuetype</var> <var>collectiontype</var>
    </div>

    <p>for collections, and</p>

    <div style="padding: 1em">
      <var>keytype</var> 2 <var>valuetype</var> <var>maptype</var>
    </div>

    <p>for maps.

    <p>The word "type" here referes to a capitalized primitive type, {@link
    java.lang.Object} or <code>Reference</code>. In the latter case, we
    are treating objects, but their equality is established by reference
    equality (that is, without invoking <code>equals()</code>), similarly
    to {@link java.util.IdentityHashMap}. Note that reference-based
    classes are significantly faster.</p>

    <p>Thus, an {@link it.unimi.dsi.fastutil.ints.IntOpenHashSet} stores
    integers efficiently and implements {@link
    it.unimi.dsi.fastutil.ints.IntSet}, whereas a {@link
    it.unimi.dsi.fastutil.longs.Long2IntAVLTreeMap} does the same for maps from
    longs to integers (but the map will be sorted, tree based, and balanced
    using the AVL criterion), implementing {@link
    it.unimi.dsi.fastutil.longs.Long2IntMap}. If you need additional
    flexibility in choosing your {@linkplain
    it.unimi.dsi.fastutil.Hash.Strategy hash strategy}, you can put, say, arrays
    of integers in a {@link it.unimi.dsi.fastutil.objects.ObjectOpenCustomHashSet},
    maybe using the ready-made {@linkplain
    it.unimi.dsi.fastutil.ints.IntArrays#HASH_STRATEGY hash strategy for
    arrays}.  A {@link it.unimi.dsi.fastutil.longs.LongLinkedOpenHashSet}
    stores longs in a hash table, but provides a predictable iteration order
    (the insertion order) and access to first/last elements of the order. A
    {@link it.unimi.dsi.fastutil.objects.Reference2ReferenceOpenHashMap} is
    similar to an {@link java.util.IdentityHashMap}. You can manage a priority
    queue of characters in a heap using a {@link
    it.unimi.dsi.fastutil.chars.CharHeapPriorityQueue}, which implements {@link
    it.unimi.dsi.fastutil.chars.CharPriorityQueue}.  {@linkplain
    it.unimi.dsi.fastutil.bytes.ByteArrayFrontCodedList Front-coded lists} are
    highly specialized immutable data structures that store compactly a large
    number of arrays: if you don't know them you probably don't need them.

    <p>For a number of data structures that were not available in the
    <a href="http://java.sun.com/j2se/1.5/docs/guide/collections/">Java&trade; Collections Framework</a>
    when <code>fastutil</code> was created, an object-based version is
    contained in {@link it.unimi.dsi.fastutil}, and in that case the prefix
    <code>Object</code> is not used (see, e.g., {@link it.unimi.dsi.fastutil.PriorityQueue}).

    <p>Since there are eight primitive types in Java, and we support
    reference-based containers, we get around 2000 (!) classes (some nonsensical
    classes, such as <code>Boolean2BooleanAVLTreeMap</code>, are not
    generated). Many classes are generated just to mimic the hierarchy of
    {@link java.util} so to redistribute common code in a similar way. There
    are also several abstract classes that ease significantly the creation of
    new type-specific classes by providing automatically generic methods based
    on the type-specific ones.</p>

    <p>The huge number of classes required a suitable division in subpackages.
    Each subpackage is characterized by the type of elements
    or keys: thus, for instance, {@link it.unimi.dsi.fastutil.ints.IntSet}
    belongs to {@link it.unimi.dsi.fastutil.ints} (the plural is required, as
    <code>int</code> is a keyword and cannot be used in a package name), as
    well as {@link it.unimi.dsi.fastutil.ints.Int2ReferenceRBTreeMap}. Note
    that all classes for non-primitive elements and keys are gathered in {@link
    it.unimi.dsi.fastutil.objects}. Finally, a number of non-type-specific
    classes have been gathered in {@link it.unimi.dsi.fastutil}.


    <h2>An In&ndash;Depth Look</h2>

    <p>The following table summarizes the available interfaces and
    implementations. To get more information, you can look at a specific
    implementation in {@link
    it.unimi.dsi.fastutil} or, for instance, {@link it.unimi.dsi.fastutil.ints}. Note that a few existing
    abstract classes have been deprecated and are not listed here (they are no longer necessary due to
    default methods in the corresponding interfaces).

    <div>
    <table border=1>
	<caption>Interfaces and Abstract Implementations</caption>
    <tr><th>Interfaces<th>Abstract Implementations<th>Implementations
    <tr><td>Iterable
    <tr><td>Collection<td>AbstractCollection
    <tr><td>Set<td>AbstractSet<td>OpenHashSet, OpenCustomHashSet, ArraySet, OpenHashBigSet
    <tr><td>SortedSet<td>AbstractSortedSet<td>RBTreeSet, AVLTreeSet, LinkedOpenHashSet
    <tr><td>Function<td>AbstractFunction<td>
    <tr><td>Map<td>AbstractMap<td>OpenHashMap, OpenCustomHashMap, ArrayMap
    <tr><td>SortedMap<td>AbstractSortedMap<td>RBTreeMap, AVLTreeMap, LinkedOpenHashMap
    <tr><td>List, BigList&dagger;<td>AbstractList, AbstractBigList<td>ArrayList, BigArrayBigList, MappedBigList, ArrayFrontCodedList, ImmutableList
    <tr><td>PriorityQueue&dagger;<td><td>HeapPriorityQueue, ArrayPriorityQueue, ArrayFIFOQueue
    <tr><td>IndirectPriorityQueue&dagger;<td><td>HeapSemiIndirectPriorityQueue, HeapIndirectPriorityQueue, ArrayIndirectPriorityQueue
    <tr><td>Stack&dagger;<td><td>ArrayList
    <tr><td>Pair&dagger;<td><td>MutablePair, ImmutablePair
    <tr><td>Iterator, BigListIterator&dagger;<td>Iterators.AbstractIndexBasedIterator
    <tr><td>Spliterator<td>Spliterators.AbstractIndexBasedSpliterator
    <tr><td>Comparator
    <tr><td>BidirectionalIterator&dagger;
    <tr><td>ListIterator
    <tr><td>Consumer
    <tr><td>BiConsumer
    <tr><td>Predicate
    <tr><td>BinaryOperator
    <tr><td>Size64&Dagger;
    </table>
    </div>

    <p>&dagger;: this class has also a non-type-specific implementation in {@link it.unimi.dsi.fastutil}.
    <p>&Dagger;: this class has <em>only</em> a non-type-specific implementation in {@link it.unimi.dsi.fastutil}.

    <p>Note that abstract implementations are named by prefixing the interface
    name with {@code Abstract}. Thus, if you want to define a
    type-specific structure holding a set of integers without the hassle of
    defining object-based methods, you should inherit from {@link it.unimi.dsi.fastutil.ints.AbstractIntSet}.

    <p>The following table summarizes static containers, which usually give rise
    both to a type-specific and to a generic class:

    <div>
    <table border=1 style="border: solid thin black">
	<caption>Static Containers</caption>
    <tr><th>Static Containers
    <tr><td>Collections
    <tr><td>Sets
    <tr><td>SortedSets
    <tr><td>Functions
    <tr><td>Maps&dagger;
    <tr><td>SortedMaps
    <tr><td>Lists
    <tr><td>BigLists
    <tr><td>Arrays&dagger;
    <tr><td>BigArrays&dagger;
    <tr><td>Heaps
    <tr><td>SemiIndirectHeaps
    <tr><td>IndirectHeaps
    <tr><td>PriorityQueues&dagger;
    <tr><td>IndirectPriorityQueues&dagger;
    <tr><td>Iterators
    <tr><td>BigListIterators
    <tr><td>Spliterators
    <tr><td>BigSpliterators
    <tr><td>Comparators
    <tr><td>Hash&Dagger;
    <tr><td>HashCommon&Dagger;
    <tr><td>SafeMath&Dagger;
    </table>
    </div>

    <p>&dagger;: this class has also a non-type-specific implementation in {@link it.unimi.dsi.fastutil}.
    <p>&Dagger;: this class has <em>only</em> a non-type-specific implementation in {@link it.unimi.dsi.fastutil}.

    <p>The static containers provide also special-purpose implementations for
    all kinds of {@linkplain it.unimi.dsi.fastutil.objects.ObjectSets#EMPTY_SET
    empty structures} (including {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectArrays#EMPTY_ARRAY arrays}) and
    {@linkplain it.unimi.dsi.fastutil.ints.Int2IntMaps#singleton(int,int) singletons}.


    <h2>Warnings</h2>

    <p><strong>All classes are not synchronized</strong>. If multiple threads
    access one of these classes concurrently, and at least one of the threads
    modifies it, it must be synchronized externally. Iterators will behave
    unpredictably in the presence of concurrent modifications. Reads, however,
    can be carried out concurrently.

    <p><strong>Reference-based classes violate the {@link java.util.Map}
    contract</strong>. They intentionally compare objects by reference, and do
    not use the <code>equals()</code> method. They should be used only
    when reference-based equality is desired (for instance, if all
    objects involved are canonized, as it happens with interned strings).

    <p><strong>Setting the default return value for maps with both non-primitive
	keys and non-primitive values violates the {@link java.util.Map} contract</strong>, as you
    might not get <code>null</code> on missing keys.

    <p><strong>Linked classes do not implement wholly the {@link
    java.util.SortedMap} interface</strong>. They provide methods to get the
    first and last element in iteration order, and to start a bidirectional
    iterator from any element, but any submap or subset
    method will cause an {@link java.lang.UnsupportedOperationException}
    (this may change in future versions).

    <p><strong>Substructures in sorted classes allow the creation of
    arbitrary substructures</strong>. In {@link java.util}, instead, you
    can only create contained sub-substructures (BTW, why?). For instance,
    <code>(new TreeSet()).tailSet(1).tailSet(0)</code> will throw an exception,
    but {@link it.unimi.dsi.fastutil.ints.IntRBTreeSet (new
    IntRBTreeSet()).tailSet(1).tailSet(0)} won't.


    <h2>Additional Features and Methods</h2>

    <p>The new interfaces add some very natural methods and strengthen many of
    the old ones. Moreover, whenever possible, the object returned is
    type-specific, or implements a more powerful interface.

    <p>More in detail:
    <ul>

    <li>Keys and values of a map are of the <code>fastutil</code> type you
    would expect (e.g., the keys of an {@link
    it.unimi.dsi.fastutil.ints.Int2LongSortedMap} are an {@link
    it.unimi.dsi.fastutil.ints.IntSortedSet} and the values are a {@link
    it.unimi.dsi.fastutil.longs.LongCollection}).

    <li>Hash-based and tree-based maps that return primitive numeric values have an <code>addTo()</code>
    method (see, e.g., {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap#addTo(int,int)})
    that <em>adds</em> an increment to the current value of a key; it is
    most useful to avoid the inefficient procedure of getting a value,
    incrementing it and then putting it back into the map (typically, when
    counting the number of occurrences of elements in a sequence).

    <li>Hash-set implementations have an additional {@link it.unimi.dsi.fastutil.objects.ObjectOpenHashSet#get(Object) get()}
    method that returns the actual object in the collection that is equal to the query key.

    <li>Linked hash-based maps and sets have a wealth of additional methods that make it easy
    to use them as caches. See, for instance, {@link it.unimi.dsi.fastutil.ints.Int2IntLinkedOpenHashMap#putAndMoveToLast(int,int)},
    {@link it.unimi.dsi.fastutil.ints.IntLinkedOpenHashSet#addAndMoveToLast(int)}
    or {@link it.unimi.dsi.fastutil.ints.Int2IntLinkedOpenHashMap#removeFirstInt()}.

    <li>Submaps of a sorted map and subsets of a sorted sets are of the
    <code>fastutil</code> type you would expect, too.

    <li>Iterators returned by <code>iterator()</code> are type-specific.
    
    <li>Spliterators returned by <code>spliterator()</code> are type-specific.

	<li>Collection has a method returning primitive streams, for example {@link it.unimi.dsi.fastutil.ints.IntCollection#intStream()}.  

    <li>Sorted structures in <code>fastutil</code> return
    type-specific {@linkplain
    it.unimi.dsi.fastutil.BidirectionalIterator bidirectional
    iterators}. This means that you can move back and forth among
    entries, keys or values.

    <li>Some classes for maps (check the specification) return a <em>fast entry set</em>
    (see, e.g., {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap#int2IntEntrySet()});
    fast entry sets can, in turn, provide a <em>{@linkplain it.unimi.dsi.fastutil.ints.Int2IntMap.FastEntrySet#fastIterator() fast iterator}</em>
    that is guaranteed not to create a large number of objects, <em>possibly by returning always the same entry</em> (of course, mutated).
	There's a also companion {@link it.unimi.dsi.fastutil.ints.Int2IntMap.FastEntrySet#fastForEach(java.util.function.Consumer) fastForEach()}.
    To make it possible to access these fast iterators in <code>for</code> loops, there are static helper methods available
    (e.g., {@link it.unimi.dsi.fastutil.ints.Int2IntMaps#fastIterable(it.unimi.dsi.fastutil.ints.Int2IntMap)}).

    <li>The type-specific sorted set interfaces, moreover, feature an optional
    method <code>iterator(from)</code> which creates a type-specific {@link
    it.unimi.dsi.fastutil.BidirectionalIterator} starting from a given
    element of the domain (not necessarily in the set). See, for instance,
    {@link it.unimi.dsi.fastutil.ints.IntSortedSet#iterator(int)}. The method is
    implemented by all type-specific sorted sets and subsets.

    <li>Finally, there are constructors that allow you to build easily sets
    using array and iterators. This means, for instance, that you can create
    quickly a set of strings with a statement like
    <blockquote>
      <code>new ObjectOpenHashSet( new String[] { "foo", "bar" } )</code>
    </blockquote>
    or just "unroll" the integers returned by an iterator into a list with
    <blockquote>
      <code>new IntArrayList( iterator )</code>
    </blockquote>

    </ul>

    <p>There are a few quirks, however, that you should be aware of:

    <ul>

    <li>The versions of the {@link java.util.Map#get(Object)
    get()}, {@link java.util.Map#put(Object,Object) put()} and
    {@link java.util.Map#remove(Object) remove()} methods that
    return a primitive type cannot, of course, rely on returning
    <code>null</code> to denote the absence of a certain
    pair. Rather, they return a <em>{@linkplain
    it.unimi.dsi.fastutil.ints.Int2LongMap#defaultReturnValue(long) default
    return value}</em>, which is set to 0 cast to the
    return type (<code>false</code> for booleans) at creation, but
    can be changed using the <code>defaultReturnValue()</code>
    method (see, e.g., {@link
    it.unimi.dsi.fastutil.ints.Int2IntMap}). Note that changing the
    default return value does not change anything about the data
    structure; it is just a way to return a reasonably meaningful
    result&mdash;it can be changed at any time. For uniformity reasons,
    even maps returning objects can use
    <code>defaultReturnValue()</code> (of course, in this case the
    default return value is initialized to <code>null</code>). A
    submap or subset has an independent default return value (which
    however is initialized to the default return value of the
    originator).</li>

    <li>For all maps that have objects as keys, the {@link
    java.util.Map#get(Object) get()} and {@link
    java.util.Map#remove(Object) remove()} methods do not admit
    polymorphic versions, as Java does not allow return-value
    polymorphism. Rather, the extended interfaces introduce new
    methods of the form {@link
    it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap#getInt(Object)
    get<var>valuetype</var>()} and {@link
    it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap#removeInt(Object)
    remove<var>valuetype</var>()}. Similar problems occur with
    {@link it.unimi.dsi.fastutil.chars.CharSortedSet#firstChar()
    first()}, {@link
    it.unimi.dsi.fastutil.chars.CharSortedSet#lastChar() last()},
    and so on.</li>

    <li>Similarly, all iterators have a suitable method {@link
    it.unimi.dsi.fastutil.ints.IntIterator#nextInt()
    next<var>type</var>()} returning directly a primitive type.
    And, of course, you have a type-specific version of {@link
    java.util.ListIterator#previous() previous()}. Note that the &ldquo;for each&rdquo;
	style of iteration can hide boxing and unboxing: even if you iterate
	using a primitive variable (as in {@code for(long x: s)}, where {@code s}
	is a {@link it.unimi.dsi.fastutil.longs.LongSet}), the actual iterator used will be
	object-based, as Java knows nothing about <code>fastutil</code>'s
	type-specific {@code next()}/{@code previous()} methods.

    <li>For the same reason, the method {@link java.util.Collection#toArray}
    as a polymorphic version accepting a type-specific array, but there is
    also an explicitly typed method
    {@link it.unimi.dsi.fastutil.bytes.ByteCollection#toByteArray()
    to<var>keytype</var>Array()}.</li>

    <li>The standard entry-set iterators for hash-based maps use an entry object
    that refers to the data contained in the hash table. If you retrieve an
    entry and delete it, the entry object will become invalid and will throw
    an {@link java.lang.ArrayIndexOutOfBoundsException} exception. This does not
    apply to fast iterators (see above).</li>

    <li>A name clash between the list and collection interfaces
    forces the deletion method of a collection to be named {@link
    it.unimi.dsi.fastutil.doubles.DoubleCollection#rem(double)
    rem()}. At the risk of creating some confusion, {@link
    it.unimi.dsi.fastutil.doubles.DoubleSet#remove(double) remove()}
    reappears in the type-specific set interfaces, so the only
    really unpleasant effect is that you must use
    <code>rem()</code> on variables that are collections, but not
    sets&mdash;for instance, {@linkplain
    it.unimi.dsi.fastutil.ints.IntList type-specific lists}, and
    that a subclass of a type-specific abstract collection must
    override <code>rem()</code>, rather than <code>remove()</code>, to
    make all inherited methods work properly.</li>

    <li>Stacks are <em>interfaces</em> implemented by array-based
    lists: the interface, moreover, is slightly different from the
    implementation contained in {@link java.util.Stack}.</li>

    <li>In JDK 8 a number of classes appeared specifying primitive-type
    interfaces: examples are {@link java.util.PrimitiveIterator} and
    {@link java.util.function.IntToLongFunction}. Whenever possible,
    <code>fastutil</code> tries to extend such interfaces (e.g.,
    {@link it.unimi.dsi.fastutil.ints.IntIterator} extends
    {@link java.util.PrimitiveIterator.OfInt}).</li>

    <li>In the specification of new methods such as
    {@link java.util.Map#computeIfAbsent(Object,java.util.function.Function)
    Map.computeIfAbsent()} we do not always have a suitable type-specific
    version of {@link java.util.function.Function} in the JDK: in this case,
    we approximate the best we can. For example, a
    {@link it.unimi.dsi.fastutil.bytes.Byte2ByteMap} expects an
    {@link java.util.function.IntUnaryOperator}. The default implementation
    will check that the returned argument actually fits a byte, throwing an
    exception otherwise. Note that we always specify also a version
    accepting a function returning an object, as it is useful in case
    one needs to return {@code null}.</li>

    <li>In the specification of new methods requiring a type-specific
    {@link java.util.function.Consumer} such as {@link java.lang.Iterable#forEach(java.util.function.Consumer)}
    we try to use the {@link java.util.function} correct type, if available. Otherwise, we use
    the <code>fastutil</code> correct type-specific version, but, as in the previous case,
    the <code>fastutil</code> version extends the closest {@link java.util.function.Consumer}.
    For example, {@link it.unimi.dsi.fastutil.chars.CharConsumer} extends
    {@link java.util.function.IntConsumer}.</li>
    </ul>


    <h2>Functions</h2>

    {@link it.unimi.dsi.fastutil.Function} (and its type-specific versions) is an
    interface geared towards mathematical functions (e.g., hashes) which associates
    values to keys, but in which enumerating keys or values is not possible. It is essentially
    a {@link java.util.Map} that does not provide access to set representations. It is of course
    unfortunate that Java 8 introduced an identically named interface with a different signature:
    differences and interoperability issues are discussed in the
    {@linkplain it.unimi.dsi.fastutil.Function class documentation}.

    <p><code>fastutil</code>
    provides interfaces, abstract implementations and the usual array of wrappers
    in the suitable static container (e.g., {@link it.unimi.dsi.fastutil.ints.Int2IntFunctions}).
    Implementations will be provided by other projects (e.g., <a href="http://sux.di.unimi.it/">Sux4J</a>).
    Type-specific functions require just to define their {@code get()} methods: thus, they can be defined
    by lambda expressions.

    <p>All <code>fastutil</code> type-specific maps extend their respective type-specific
    functions: but, alas, we cannot have {@link java.util.Map} extending
    {@link it.unimi.dsi.fastutil.Function}. Moreover, type-specific
    functions extend the existing type-specific function from {@link
    java.util.function} that can accommodate the argument and the result with the least
    widening: for example, {@link
    it.unimi.dsi.fastutil.shorts.Short2CharFunction} extends {@link
    java.util.function.IntUnaryOperator}.


    <h2>Static Container Classes</h2>

    <p><code>fastutil</code> provides a number of static methods and
    singletons, much like {@link java.util.Collections}. To avoid creating
    classes with hundreds of methods, there are separate containers for
    sets, lists, maps and so on. Generic containers are placed in {@link
    it.unimi.dsi.fastutil}, whereas type-specific containers are in the
    appropriate package.  You should look at the documentation of the
    static classes contained in {@link it.unimi.dsi.fastutil}, and in
    type-specific static classes such as {@link
    it.unimi.dsi.fastutil.chars.CharSets}, {@link
    it.unimi.dsi.fastutil.floats.Float2ByteSortedMaps}, {@link
    it.unimi.dsi.fastutil.longs.LongArrays}, {@link
    it.unimi.dsi.fastutil.floats.FloatHeaps}.  Presently, you can easily
    obtain {@linkplain it.unimi.dsi.fastutil.objects.ObjectSets#EMPTY_SET empty collections},
    {@linkplain it.unimi.dsi.fastutil.longs.Long2IntMaps#EMPTY_MAP empty
    type-specific collections}, {@linkplain
    it.unimi.dsi.fastutil.ints.IntLists#singleton(int) singletons},
    {@linkplain
    it.unimi.dsi.fastutil.objects.Object2ReferenceSortedMaps#synchronize(Object2ReferenceSortedMap)
    synchronized versions} of any type-specific container and
    unmodifiable versions of       {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectLists#unmodifiable(ObjectList)
    containers} and   {@linkplain
    it.unimi.dsi.fastutil.ints.IntIterators#unmodifiable(IntBidirectionalIterator) iterators} (of course,
    unmodifiable containers always return unmodifiable iterators).

    <p>On a completely different side, the {@linkplain
    it.unimi.dsi.fastutil.ints.IntArrays type-specific static container
    classes for arrays} provide several useful methods that allow to treat
    an array much like an array-based list, hiding completely the growth
    logic. In many cases, using this methods and an array is even simpler
    then using a full-blown {@linkplain
    it.unimi.dsi.fastutil.doubles.DoubleArrayList type-specific
    array-based list} because elements access is syntactically much
    simpler. The version for objects uses reflection to return arrays of
    the same type of the argument.

    <p>For the same reason, <code>fastutil</code> provides a full
    implementation of methods that manipulate arrays as type-specific
    {@linkplain it.unimi.dsi.fastutil.ints.IntHeaps heaps}, {@linkplain
    it.unimi.dsi.fastutil.ints.IntSemiIndirectHeaps semi-indirect heaps} and
    {@linkplain it.unimi.dsi.fastutil.ints.IntIndirectHeaps indirect heaps}. There are
    also quicksort and mergesort implementations that use arbitrary type-specific comparators.

    <p><code>fastutil</code> offers also a less common choice&mdash;a very tuned
    implementation of {@linkplain it.unimi.dsi.fastutil.ints.IntArrays#radixSort(int[],int,int) radix sort} for
    all primitive types. It is significantly faster than quicksort already at small sizes (say, more than 10000 elements), and should
    be considered the sorting algorithm of choice if you do not need a generic comparator.

    <p>There are several variants provided. First of all you can radix sort in parallel
    {@linkplain it.unimi.dsi.fastutil.ints.IntArrays#radixSort(int[],int[], int, int) two} or
    {@linkplain it.unimi.dsi.fastutil.ints.IntArrays#radixSort(int[][],int,int) even more} arrays. You
    can also perform {@linkplain it.unimi.dsi.fastutil.ints.IntArrays#radixSortIndirect(int[],int[],int,int,boolean) indirect} sorts,
    for instance if you want to compute the sorting permutation of an array.

    <p>The sorting algorithm is a tuned radix sort adapted from Peter M. McIlroy, Keith Bostic and M. Douglas
    McIlroy, &ldquo;Engineering radix sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993),
    and further improved using the digit-oracle idea described by
    Juha K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort for strings&rdquo;,
    <i>String Processing and Information Retrieval, 15th International Symposium</i>, volume 5280 of
    Lecture Notes in Computer Science, pages 3&minus;14, Springer (2008). The basic algorithm is not
    stable, but this is immaterial for arrays of primitive types. For the indirect case, there is a parameter
    specifying whether the algorithm should be stable.


    <h2>Iterators and Comparators</h2>

    <p><code>fastutil</code> provides type-specific iterators and
    comparators. The interface of a <code>fastutil</code> iterator is
    slightly more powerful than that of a {@link java.util} iterator, as
    it contains a {@link it.unimi.dsi.fastutil.objects.ObjectIterator#skip(int)
    skip()} method that allows to skip over a list of elements (an
    {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator#back(int) analogous
    method} is provided for bidirectional iterators). For objects (even
    those managed by reference), the extended interface is named {@link
    it.unimi.dsi.fastutil.objects.ObjectIterator}; it is the return type, for
    instance, of {@link
    it.unimi.dsi.fastutil.objects.ObjectCollection#iterator()}.

    <p>A plethora of useful static methods is also provided by various
    type-specific static containers (e.g., {@link
    it.unimi.dsi.fastutil.ints.IntIterators}) and {@link
    it.unimi.dsi.fastutil.ints.IntComparators}: among other things, you can
    {@linkplain it.unimi.dsi.fastutil.ints.IntIterators#wrap(int[]) wrap
    arrays} and {@linkplain
    it.unimi.dsi.fastutil.ints.IntIterators#asIntIterator(java.util.Iterator)
    standard iterators} in type-specific iterators, {@linkplain
    it.unimi.dsi.fastutil.ints.IntIterators#fromTo(int,int) generate them}
    giving an interval of elements to be returned, {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectIterators#concat(ObjectIterator[])
    concatenate them} or {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectIterators#pour(Iterator,ObjectCollection)
    pour them} into a set.
    
    <h2>Spliterators and Streams</h2>
    <p><code>fastutil</code> provides type-specific {@linkplain java.util.Spliterator spliterators}. These are
    used to implement fast streams.

    <p>Due to Java only supporting primitive Streams of <code>int</code>, <code>long</code>,
    and <code>double</code>,
    types for primitives narrower then that (such as {@linkplain
    it.unimi.dsi.fastutil.bytes.ByteCollection ByteCollection}) have methods
    that expose a spliterator widening them to the type supported by the
    Stream API. For example, {@linkplain it.unimi.dsi.fastutil.bytes.ByteCollection ByteCollection}
    will have an {@link it.unimi.dsi.fastutil.bytes.ByteCollection#intSpliterator intSpliterator()}
    method in addition to a <code>spliterator()</code> method that works in terms of
    bytes.
    
    <p>Due to the incompatibility of object based {@linkplain java.util.stream.Stream streams} and the
    primitive streams (such as {@link java.util.stream.IntStream}), the <code>stream()</code>
    methods of the primitive containers could not be updated to return their
    primitive equivalents. Instead, for primitive collections, a new method is
    provided that exposes a primitive stream, and the object based stream method
    is marked deprecated like the other boxing methods do.
    For example, {@linkplain it.unimi.dsi.fastutil.bytes.ByteCollection},
    {@linkplain it.unimi.dsi.fastutil.shorts.ShortCollection}, and
    {@linkplain it.unimi.dsi.fastutil.ints.IntCollection} exposes an
    {@link it.unimi.dsi.fastutil.ints.IntCollection#intStream() intStream()} method, which should
    be used in preference to
    <code>stream()</code> as it will not box and unbox.

	<p>Since type-specific {@link java.util.stream.Collector collectors} would be
	more than 700, <code>fastutil</code> implements basic collection
	methods in each container (e.g., {@link
	it.unimi.dsi.fastutil.ints.IntImmutableList#toList(java.util.stream.IntStream)
	IntImmutableList.toList()}). These methods must be applied to a stream
	to obtain a collection containing the output of the stream.
    
    <p>Similar to iterators, a raft of utility methods for type-specific spliterators are provided
    (e.g. {@link it.unimi.dsi.fastutil.ints.IntSpliterators}).  Most of them are analogues of the
    utilities in the type-specific <code>Iterators</code> class.
    
    <p>Currently no utility methods are provided for type-specific streams, as the
    Java library's API already has good coverage for that (e.g. the static methods of
    {@link java.util.stream.Stream} and their primitive equivalents, or classes such as
    {@link java.util.stream.StreamSupport}).


	<h2>Functions, Consumers, Predicates, and Operators</h2>

	<p>Classes such as {@link java.util.function.IntBinaryOperator} were introduced in Java 8
	to obtain performance improvements similar to those obtained by <code>fastutil</code>. Unfortunately,
	the design of all these classes follows an opposite choice with respect to <code>fastutil</code>'s:
	type-specific classes do not extend the generic ones. Moreover, type specificity is rather limited
	(e.g., there are no short-specific classes). The fact that type-specific classes do not extend
	generic ones makes it difficult to use lambdas, as often they are (rightly) considered
	ambiguous by the compiler. The solution implemented in <code>fastutil</code> 8.5.0 is to have
	an internal type-specific version of these interfaces which extends both the generic one
	and the JDK type-specific one, allowing also for type widening (e.g., {@link it.unimi.dsi.fastutil.chars.CharConsumer}
	extends {@link java.util.function.IntConsumer}). When definining lambdas, the compiler now
	has a more specific type to choose (the type-specific <code>fastutil</code> interface), and
	no ambiguity arises.

    <h2>Queues</h2>

    <p><code>fastutil</code> offers two types of queues: <em>direct
    queues</em> and <em>indirect queues</em>. A direct queue offers type-specific method to {@linkplain
    it.unimi.dsi.fastutil.longs.LongPriorityQueue#enqueue(long) enqueue} and
    {@linkplain it.unimi.dsi.fastutil.longs.LongPriorityQueue#dequeueLong()
    dequeue} elements. An indirect queue needs a <em>reference array</em>,
    specified at construction time: {@linkplain
    it.unimi.dsi.fastutil.IndirectPriorityQueue#enqueue(int) enqueue} and
    {@linkplain it.unimi.dsi.fastutil.IndirectPriorityQueue#dequeue()
    dequeue} operations refer to indices in the reference array. The advantage
    is that it may be possible to {@linkplain
    it.unimi.dsi.fastutil.IndirectPriorityQueue#changed(int) notify the change}
    of any element of the reference array, or even to {@linkplain
    it.unimi.dsi.fastutil.IndirectPriorityQueue#remove(int) remove an arbitrary
    element}.

    <p>Queues have two kind of implementations: array-based
    implementations, and heap-based implementations. In particular, heap-based
    indirect queues may be {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectHeapIndirectPriorityQueue fully
    indirect} or just {@linkplain
    it.unimi.dsi.fastutil.objects.ObjectHeapSemiIndirectPriorityQueue
    semi-indirect}: in the latter case, there is no need for an explicit
    indirection array (which saves one integer per queue entry), but not all
    operations will be available. Note there there are also
    {@linkplain it.unimi.dsi.fastutil.ints.IntArrayFIFOQueue FIFO queues}.


    <h2>Custom Hashing</h2>

    <p>Sometimes, the behaviour of the built-in equality and hashing methods is
    not what you want. In particular, this happens if you store in a hash-based
    collection arrays, and you would like to compare them by equality. For this kind of applications,
    <code>fastutil</code> provides {@linkplain it.unimi.dsi.fastutil.Hash.Strategy custom hash strategies},
    which define new equality and hashing methods to be used inside the collection. There are even
    {@linkplain it.unimi.dsi.fastutil.ints.IntArrays#HASH_STRATEGY ready-made strategies} for arrays. Note, however,
    that <code>fastutil</code> containers do not cache hash codes, so custom hash strategies must be efficient.


    <h2>Abstract Classes</h2>

    <p><code>fastutil</code> provides a wide range of abstract classes, to
    help in implementing its interfaces. They take care, for instance, of
    providing wrappers for non-type-specific method calls, so that you have to
    write just the (usually simpler) type-specific version. When possible,
    such wrappers are actually default methods, so no abstract class is
    necessary.



    <h1>More on the support for very large collections</h1>

    <p>With the continuous increase in core memory available, Java arrays are starting to show
    their size limitation (indices cannot be larger than 2<sup>31</sup>). <code>fastutil</code>
    proposes to store <em>big arrays</em> using arrays-of-arrays subject to certain
    size restrictions and a number of supporting static methods. Please read the documentation
    of {@link it.unimi.dsi.fastutil.BigArrays} to understand how big arrays work.

    <p>Correspondingly, <code>fastutil</code> proposes a new interface, called
    {@link it.unimi.dsi.fastutil.Size64}, that should be implemented by very large
    collections. {@link it.unimi.dsi.fastutil.Size64} contains a method
    {@link it.unimi.dsi.fastutil.Size64#size64()} which returns the collection
    size as a long integer.

    <p><code>fastutil</code> provides {@linkplain it.unimi.dsi.fastutil.BigList big lists},
    which are lists with 64-bit indices; of course, they implement {@link it.unimi.dsi.fastutil.Size64}.
    An implementation based on big arrays is provided (see, e.g., {@link it.unimi.dsi.fastutil.ints.IntBigArrayBigList}),
    as well as static containers (see, e.g., {@link it.unimi.dsi.fastutil.ints.IntBigLists}).
    Whereas it is unlikely that such collection will be in main memory as big arrays, there
    are number of situations, such as exposing large files through a list interface or
    storing a large amount of data using <a href="http://sux4j.di.unimi.it/">succinct data structures</a>,
    in which a big list interface is natural.

    <p>Unfortunately, {@linkplain java.util.List lists} and {@linkplain it.unimi.dsi.fastutil.BigList big lists},
    as well as {@linkplain java.util.ListIterator list iterators} and {@linkplain it.unimi.dsi.fastutil.BigListIterator big-list iterators},
    cannot be made compatible: we thus provide adapters (see, e.g., {@link it.unimi.dsi.fastutil.ints.IntBigLists#asBigList(it.unimi.dsi.fastutil.ints.IntList)}).

    <p>Finally, <code>fastutil</code> provides {@linkplain it.unimi.dsi.fastutil.longs.LongOpenHashBigSet big hash sets}, which
    are based on big arrays. They are about 30% slower than non-big sets, but their size is limited only by
    the amount core memory.



    <h1>More on fast and practical I/O</h1>

    <p><code>fastutil</code> includes an {@linkplain
    it.unimi.dsi.fastutil.io I/O package} that provides, for instance, {@linkplain
    it.unimi.dsi.fastutil.io.FastBufferedInputStream fast, unsynchronized
    buffered input streams}, {@linkplain
    it.unimi.dsi.fastutil.io.FastBufferedOutputStream fast, unsynchronized
    buffered output streams}, and a wealth of static methods to store and
    retrieve data in {@linkplain it.unimi.dsi.fastutil.io.TextIO textual} and
    {@linkplain it.unimi.dsi.fastutil.io.BinIO binary} form. The latter, in particular,
    contain methods that load and store big arrays.



    <h1>Performance</h1>

    <p>The main reason behind <code>fastutil</code> is performance, both in
    time and in space. The relevant methods of type-specific hash maps and sets
    are something like 2 to 10 times faster than those of the standard
    classes. Note that performance of hash-based classes on object keys is
    usually <em>slightly worse</em> than that of
    {@link java.util}, because <code>fastutil</code> classes do not cache hash
    codes (albeit it will not be that bad if keys cache internally hash codes,
    as in the case of {@link java.lang.String}). Of course, you can try to get
    more speed from hash tables using a small load factor: to this purpose,
    alternative load factors are proposed in {@link it.unimi.dsi.fastutil.Hash#FAST_LOAD_FACTOR}
    and {@link it.unimi.dsi.fastutil.Hash#VERY_FAST_LOAD_FACTOR}.

    <p>For tree-based classes you have two choices: AVL and red-black
    trees. The essential difference is that AVL trees are more balanced (their
    height is at most 1.44 log <var>n</var>), whereas red-black trees have
    faster deletions (but their height is at most 2 log <var>n</var>). So on
    small trees red-black trees could be faster, but on very large sets AVL
    trees will shine. In general, AVL trees have slightly slower updates but
    faster searches; however, on very large collections the smaller height may
    lead in fact to faster updates, too.

    <p><code>fastutil</code> reduces enormously the creation and collection of
    objects. First of all, if you use the polymorphic methods and iterators no
    wrapper objects have to be created. Moreover, since <code>fastutil</code>
    uses open-addressing hashing techniques, creation and garbage collection of
    hash-table entries are avoided (but tables have to be rehashed whenever
    they are filled beyond the load factor). The major reduction of the number
    of objects around has a definite (but very difficult to measure) impact on
    the whole application (as garbage collection runs proportionally to the
    number of alive objects).

    <p>Maps whose iteration is very expensive in terms of object creation (e.g., hash-based classes) usually
    return a type-specific {@link it.unimi.dsi.fastutil.ints.Int2IntMap.FastEntrySet FastEntrySet}
    whose {@link it.unimi.dsi.fastutil.ints.Int2IntMap.FastEntrySet#fastIterator() fastIterator()}
    method significantly reduces object creation by returning always
    the same entry object, suitably mutated.


    <h2>Memory Usage</h2>

    <p>The absence of wrappers makes data structures in <code>fastutil</code>
    much smaller: even in the case of objects, however, data structures in
    <code>fastutil</code> try to be space-efficient.

    <h3>Hash Tables</h3>

    <p>To avoid memory waste, (unlinked) hash tables in
    <code>fastutil</code> keep no additional information about elements
    (such as a list of keys). In particular, this means that enumerations
    are always linear in the size of the table (rather than in the number
    of keys). Usually, this would imply slower iterators. Nonetheless, the
    iterator code includes a single, tight loop; moreover, it is possible
    to avoid the creation of wrappers. These two facts make in practice
    <code>fastutil</code> iterators <em>faster</em> than {@link
    java.util}'s.

    <p>The memory footprint for a table of length &#x2113; is exactly the
    memory required for the related types times &#x2113;. The
    absence of wrappers around primitive types can reduce space occupancy by
    several times (this applies even more to serialized data, e.g., when you
    save such a data structure in a file).  These figures can greatly vary with
    your virtual machine, JVM versions, CPU etc.

    <p>More precisely, when you ask for a map that will hold <var>n</var>
    elements with load factor 0&nbsp;&lt;&nbsp;<var>f</var>&nbsp;&lt;&nbsp;1,
    2<sup>&lceil;log <var>n</var>&nbsp;/&nbsp;<var>f</var>&rceil;</sup>
    entries are allocated. When the table is filled up beyond the load factor, it is rehashed
    doubling its size. When it is emptied below <em>one fourth</em> of the load factor, it
    is rehashed halving its size; however, a map is never reduced to a
    size smaller than that at creation time: this approach makes it
    possible to create maps with a large capacity in which insertions and
    deletions do not cause immediately rehashing.

    <p>In the case of linked hash tables, there is an additional vector of
    2<sup>&lceil;log <var>n</var>&nbsp;/&nbsp;<var>f</var>&rceil;</sup> longs that is used to store link information. Each
    element records the next and previous element (packed together so to be more cache friendly).

    <h3>Balanced Trees</h3>

    <p>The balanced trees implementation is also very parsimonious.
    <code>fastutil</code> is based on the excellent (and unbelievably well
    documented) code contained in Ben Pfaff's <a
    href="https://adtinfo.org/">GNU libavl</a>, which describes in
    detail how to handle balanced trees with <em>threads</em>. Thus, the
    overhead per entry is two pointers and one integer, which compares well to
    three pointers plus one boolean of the standard tree maps. The trick is
    that we use the integer bit by bit, so we consume two bits to store thread
    information, plus one or two bits to handle balancing. As a result, we get
    bidirectional iterators in constant space and amortized constant time
    without having to store references to parent nodes.

    <p>It should be mentioned that all tree-based classes have a fixed overhead
    for some arrays that are used as stacks to simulate recursion; in
    particular, we need 48 booleans for AVL trees and 64 pointers plus 64
    booleans for red-black trees.



    <h1>Examples</h1>

	<p>To store a set of longs, we can use a hash-based container:
    <pre>
LongSet s = new LongOpenHashSet();
    </pre>
	<p>Access methods avoid boxing and unboxing:
    <pre>
s.add(1);
s.contains(2);
    </pre>
    <p>We can obtain a type-specific iterator on the elements of the set:
    <pre>
// Sum all elements
long t = 0;
for(LongIterator i = s.iterator(); i.hasNext();) t += i.nextLong();
	</pre>
	<p>Note that &ldquo;for each&rdquo; iteration must be avoided:
    <pre>
long t = 0;
for(long x: s) t += x;
	</pre>
	<p>In the loop above, boxing and unboxing is happening (even if your IDE does not report it).
	In some cases, a solution is to use a type-specific {@link java.util.Collection#forEach(java.util.function.Consumer) forEach()}:
    <pre>
// Print all elements
s.forEach(x -&gt; System.out.println(x));
	</pre>
    <p>Or we can use <code>fastutil</code>'s type-specific version of Java 8's streams:
    <pre>
long t = m.longStream().sum();
    </pre>

    <p>Suppose instead you want to store a sorted map from longs to integers. We will use a tree of AVL type:
    <pre>
Long2IntSortedMap m = new Long2IntAVLTreeMap();
    </pre>
    <p>Now we can easily modify and access its content:
    <pre>
m.put(1, 5);
m.put(2, 6);
m.put(3, 7);
m.put(1000000000L, 10);
m.get(1); // This method call will return 5
m.get(4); // This method call will return 0
    </pre>
    <p>We can also try to change the default return value:
    <pre>
m.defaultReturnValue(-1);
m.get(4); // This method call will return -1
    </pre>
    <p>We can obtain a type-specific iterator on the key set:
    <pre>
LongBidirectionalIterator i = m.keySet().iterator();
// Now we sum all keys
long s = 0;
while(i.hasNext()) s += i.nextLong();
	</pre>
    <p>Or we can use again <code>fastutil</code>'s type-specific version of Java 8's streams:
    <pre>
long s = m.longStream().sum();
    </pre>
    <p>We now generate a head map, and iterate bidirectionally over it starting
    from a given point:
    <pre>
// This map contains only keys smaller than 4
Long2IntSortedMap m1 = m.headMap(4);
// This iterator is positioned between 2 and 3
LongBidirectionalIterator t = m1.keySet().iterator(2);
t.previous(); // This method call will return 2 (t.next() would return 3)
    </pre>
    <p>Should we need to access the map concurrently, we can wrap it:
    <pre>
// This map can be safely accessed by many threads
Long2IntSortedMap m2 = Long2IntSortedMaps.synchronize(m1);
    </pre>
    <p>Linked maps are very flexible data structures which can be used to implement, for
    instance, queues whose content can be probed efficiently:
    <pre>
// This map remembers insertion order.
IntSortedSet s = new IntLinkedOpenHashSet.of(4, 3, 2, 1);
s.firstInt(); // This method call will return 4
s.lastInt(); // This method call will return 1
s.contains(5); // This method will return false
IntBidirectionalIterator i = s.iterator(s.lastInt()); // We could even cast it to a list iterator
i.previous(); // This method call will return 1
i.previous(); // This method call will return 2
s.remove(s.lastInt()); // This will remove the last element in constant time
    </pre>
    <p>Now, we play with iterators. It is easy to create iterators over
    intervals or over arrays, and combine them:
    <pre>
IntIterator i = IntIterators.fromTo(0, 10); // This iterator will return 0, 1, ..., 9
int[] a = new int[] { 5, 1, 9 };
IntIterator j = IntIterators.wrap(a); // This iterator will return 5, 1, 9.
IntIterator k = IntIterators.concat(new IntIterator[] { i , j }); // This iterator will return 0, 1, ..., 9, 5, 1, 9
    </pre>
    <p>It is easy to build lists and sets on the fly using the {@code of} static factory methods.
    For maps you can use the constructors that take key and value arrays (array based constructors for list and set exist too):
<pre>
IntSet s = IntOpenHashSet.of(1, 2, 3); // This set will contain 1, 2, and 3
Char2IntMap m = new Char2IntRBTreeMap(new char[] { '@', '-' }, new int[] { 0, 1 }); // This map will map '@' to 0 and '-' to 1
</pre>
    <p>Whenever you have some data structure, it is easy to serialize it in an
    efficient (buffered) way, or to dump their content in textual form:
    <pre>
BinIO.storeObject(s, "foo"); // This method call will save s in the file named "foo"
TextIO.storeInts(s.intIterator(), "foo.txt"); // This method call will save the content of s in ASCII
i = TextIO.asIntIterator("foo.txt"); // This iterator will parse the file and return the integers therein
	</pre>
    <p>You can also store data (of any size) in native format and access it via memory mapping:
    <pre>
BinIO.storeLongs(l, "foo", ByteOrder.nativeOrder()); // This method call will save the (big) array of longs l in the file named "foo" in native order
c = FileChannel.open(new File("foo").toPath());
m = LongMappedBigList.map(c); // Now you can access the data in l via memory mapping
	</pre>
	<p>Support for Java 8 primitive streams is included for primitive collections (e.g. {@code intStream}),
	which will work in terms of primitives instead of boxing to wrapper types like the regular {@code stream} would do:
	<pre>
IntList l = IntList.of(2, 380, 1297);
int lSum = l.intStream().sum();  // Will be 1679
IntList lTransformed = IntArrayList.toList(l.intStream().map(i -&gt; i + 40)); // Will be 42, 420, 1337
    </pre>
    <p>You can sort arrays using type-specific comparators specified by lambda expressions (no boxing/unboxing here):
    <pre>
IntArrays.quickSort(a, (x, y) -&gt; Integer.compare(y,  x)); // Sorts in reverse order
    </pre>
    <p>You can also easily specify complex generic sorting, like sorting indirectly on {@code a} while swapping elements in {@code a} and {@code b} in parallel:
    <pre>
Arrays.quickSort(0, a.length, (i, j) -&gt; Integer.compare(a[i], a[j]), (i, j) -&gt; { IntArrays.swap(a, i, j); IntArrays.swap(b, i, j); }));
    </pre>
    <p>If you have several cores, you can do it in parallel:
    <pre>
IntArrays.parallelQuickSort(a, (x, y) -&gt; y - x); // Sorts in reverse order
Arrays.parallelQuickSort(0, a.length, (i, j) -&gt; Integer.compare(a[i], a[j]), (i, j) -&gt; { IntArrays.swap(a, i, j); IntArrays.swap(b, i, j); }));
    </pre>

    <p>Some maps provide a <em>fast iterator</em> on their entry set: such iterators are allowed to reuse the {@link java.util.Map.Entry} instance
    they return, resulting is highly reduced garbage collection (e.g., for large hash maps). To easily access such iterators, we can use
    a helper static method:
    <pre>
Int2IntOpenHashMap m = new Int2IntOpenHashMap();
// Fill the map
for (Int2IntMap.Entry e : Int2IntMaps.fastIterable(m)) {
    // do things with e.getIntKey() and e.getIntValue();
}
    </pre>
    <p>The code above will not generate an object per enumerated item, as <code>for(Entry&lt;Integer,Integer&gt; e: m.entrySet())</code>
    (or even <code>for(Int2IntMap.Entry e: m.int2IntKeySet())</code>) would do.
  </body>
</html>
